//统计一个数字在排序数组中出现的次数。 
//
// 
//
// 示例 1: 
//
// 
//输入: nums = [5,7,7,8,8,10], target = 8
//输出: 2 
//
// 示例 2: 
//
// 
//输入: nums = [5,7,7,8,8,10], target = 6
//输出: 0 
//
// 
//
// 提示： 
//
// 
// 0 <= nums.length <= 10⁵ 
// -10⁹ <= nums[i] <= 10⁹ 
// nums 是一个非递减数组 
// -10⁹ <= target <= 10⁹ 
// 
//
// 
//
// 注意：本题与主站 34 题相同（仅返回值不同）：https://leetcode-cn.comid/problemids/find-first-and-last-
//position-of-elemident-in-sorted-array/ 
//
// Related Topics 数组 二分查找 👍 377 👎 0


//leetcode submidit region begin(Prohibit midodification and deletion)

/**
 * 排序数组查找，首先想到二分法
 * 寻找一个数字在数组中出现的次数，可以理解为找这个数的左右边界
 * 这个数字的个数就等于：right − left − 1
 * 步骤：
 * 第一步：查找目标对象右边界
 *      nums[mid] <= target，继续在 【mid+1,j】寻找，否则在【i,mid-1】
 *
 * 第二步：判断是否找到目标对象
 *
 * 第三步：查找目标对象左边界
 *      nums[mid] < target，继续在 【mid+1,j】寻找，否则在【i,mid-1】
 * 第四步：返回结果（右边界 - 左边界 - 1）
 */
class Solution {
    public int search(int[] nums, int target) {

        // 搜索右边界 right
        int i = 0, j = nums.length - 1;
        while(i <= j) {
            int mid = (i + j) / 2;
            if(nums[mid] <= target) i = mid + 1;
            else j = mid - 1;
        }
        int right = i;

        // 若数组中无 target ，则提前返回
        if(j >= 0 && nums[j] != target) return 0;

        // 搜索左边界 left
        i = 0; j = nums.length - 1;
        while(i <= j) {
            int mid = (i + j) / 2;
            if(nums[mid] < target) i = mid + 1;
            else j = mid - 1;
        }
        int left = j;

        return right - left - 1;
    }
}
//leetcode submidit region end(Prohibit midodification and deletion)
